Three-dimensional (“3D”) digital data may be produced by a variety of devices that involve three-dimensional scanning or sampling and/or numerical modeling. For example, computed tomography (CT) and magnetic resonance imaging (MRI) devices scan portions of the human body and generate image slices of the body, which when combined or stacked, generate a 3D representation of the body, including its surface and internal volume.
Volume graphics represent a promising way to achieve the degree of realism required for high quality 3D simulations and visualization applications because volume models can contain all the surface and internal characteristics of a real object. This is in contrast to, for example, polygon-based graphics, which contain only the information about the surfaces of a 3D object. In the case of volume graphics, volume elements (i.e., “voxels”) are the base data used to represent 3D objects. Typically, voxels are simply pixels that have a third coordinate z in addition to x and y coordinates in a Cartesian coordinate system (though voxels may take various other forms, also). In other words, voxels are equally sized cubes that form a discretely defined 3D space. A typical voxel-based 3D scene can consist of one or more “voxel sets”, each of which in turn consists of one or more voxels. For example, the 3D scene may include one or more sets of MRI slices, each forming a voxel set, which in turn includes a plurality of voxels within each voxel set.
3D voxel data are rendered to produce a 2D image on a suitable output device, such as a video display or a printer. As used herein, the term “render” means to produce a 2D graphics image on an output device from a 3D voxel data file, and typically involves creating an image using color, texture, etc., to give the image a realistic look. In typical applications of voxel-based technologies, only one voxel set is rendered, or one voxel set is rendered independently from any other voxel sets. For example, in medical MRI applications, only a single voxel set representing a single MRI slice (or a single collection of MRI slices) is rendered at a time.
In other applications, such as in rendering voxel data produced using software available from NGRAIN Corp. of Vancouver B.C., Canada, it is often necessary to render (sometimes a large number of) multiple voxel sets at a time. Briefly, NGRAIN® technology permits 3D modeling of an object, wherein each of multiple parts or layers forming the object can be represented as a voxel set each consisting of one or more voxels. Thus, according to NGRAIN® technology, it is possible to manipulate each part or layer independently from each other or from the object as a whole, in 3D space, such as to create an exploded view of the object to show the details of its parts, or to peel off an outer layer of the object to reveal its inner layer. Various details of NGRAIN® technology are described in commonly owned Patent Cooperation Treaty Application Serial No. PCT/CA01/01010 (Publication No. WO 02/07088A2) entitled “LIGHTING ADJUSTMENT METHODS AND APPARATUS FOR VOXEL DATA,” commonly owned Patent Cooperation Treaty Application Serial No. PCT/CA01/00997 (Publication No. WO 02/07089A2) entitled “APPARATUS AND METHOD FOR ASSOCIATING VOXEL INFORMATION WITH DISPLAY POSITIONS,” and in commonly owned Patent Cooperation Treaty Application Serial No. PCT/CA01/00686 (Publication No. WO 02/07097A1) entitled “METHOD, APPARATUS, SIGNALS AND CODES FOR ESTABLISHING AND USING DATA STRUCTURE FOR STORING VOXEL INFORMATION,” which are all specifically incorporated herein by reference. Additional details of NGRAIN® technology can also be found in an article, “Myths and Truths of Interactive Volume Graphics”, a paper that has been submitted to I/ITSEC 2004 Conference.
FIG. 1 illustrates an object 10 in the form of an airplane, which consists of three voxel sets A, B, and C. Although FIG. 1 is illustrated in 2D for the purpose of clarity, it should be appreciated by one skilled in the art that the actual voxel sets A, B, C are present in 3D space. In the illustrated example, voxel set A represents the body of an airplane, while voxel sets B and C represent the two wings of the airplane, respectively. Each voxel within a voxel set is defined by its geometric location, for example, in (x, y, z) in Cartesian coordinate system. Each voxel is associated with a set of attributes, such as its shade information including color and alpha values, normal vector, texture, part/layer number (i.e., to which voxel set it belongs), etc. Voxels that are occupied by an object are termed occupied voxels, whereas voxels that are not occupied are termed empty voxels. Each voxel set may contain occupied voxels and/or empty voxels. In typical surface-based applications, where only the surfaces of an object are represented in voxels, each voxel set may be up to about 90% empty, while in volume-based applications, where an object including its internal structure is represented in voxels, each voxel set may contain a lesser percentage of empty voxels. In the example of FIG. 1, which shows an airplane object 10 in surface-based voxel model, only those voxels 8 that generally define the surfaces of the object 10 are occupied, while a majority of the voxels 9 within each voxel set (A, B, or C) are empty.
FIG. 2 illustrates three voxel sets A, B, and C, which may be considered as corresponding to voxel sets A, B, and C of the airplane object 10 shown in FIG. 1. Again, although voxel sets A, B, and C are illustrated in 2D for the purpose of clarity, it should be appreciated by one skilled in the art that the actual voxel sets are in 3D space.
Typically, multiple voxel sets are rendered sequentially one after another, because each voxel set constitutes a discrete unit (e.g., a part or layer) for the purpose of various manipulations, as described above. The order in which voxel sets are to be rendered may be determined in various ways. One example is to take the midpoint of each voxel set and sort the voxel sets based on the locations of the midpoints from the closest to the farthest away from the view point 25 (or orthographically from the viewport 26). As used herein, a viewport means a view of an image. For example, in FIG. 2, voxel sets A, B, and C have midpoints 20, 22, and 24, respectively, and the midpoints 20, 22, and 24 are distanced farther away from the viewport 26 in this order. Thus, in rendering, voxel set A is rendered first, then voxel set B, and then finally voxel set C.
If a pixel in the viewport 26 has already been fully painted by the front-most voxel set(s), then no more painting of this pixel is necessary from any farther-back voxel sets. In cases where voxel sets are far apart from each other and therefore one voxel set will always appear to be in front of another voxel set as seen from the viewport 26, as shown in FIG. 2, such rendering scheme does not create any significant rendering error. For example, as shown in FIG. 2, after the front-most voxel set A is rendered to paint the pixel set A′ on the viewport 26, voxel set B is rendered to paint the pixel set B′, then voxel set C is rendered to paint the pixel set C′, creating an image as seen from the viewport 26. The above example is simplified by assuming that all the voxels in voxel sets A, B, and C are occupied, in order to illustrate the order of rendering and regions painted—the typical occupied and unoccupied voxel scenario is elaborated below.
FIG. 3 illustrates a situation where voxel sets A, B, and C are relatively closer together to collide with each other either physically or along the line of sight. This is the case of “voxel set interpenetration,” wherein certain voxels in voxel set A are in front of the other voxel set B, while other voxels in the same voxel set A are behind voxel set B. As before, voxel sets A, B, and C are rendered in this order according to the locations of their respective midpoints. Thus, voxel set A is rendered to paint the pixel set A′ on the viewport 26, then voxel set B is rendered to paint the pixel set B′, and finally voxel set C is rendered to paint the pixel set C′. Note that a portion 26 of voxel set B and a portion 27 of voxel set C are both closer to, and therefore should be visible in the viewport 26 (assuming that these portions 26 and 27 represent occupied voxels), than portions 28 and 29 in voxel set A, respectively. Yet, because voxel set A was rendered first and thus the pixel set A′ was fully painted by voxel set A, the portion 26 in voxel set B and the portion 27 in voxel set C are not rendered onto the viewport 26. This creates popping artifacts over a sequence of frames in the rendered images, because some image contents that are supposed to be behind others may unnaturally pop up to the front, or some image contents that are supposed to be in front of others may be unnaturally hidden behind others to create a hole. Thus, the voxel set interpenetration generally degrades the accuracy of the rendered image if untreated.
It should be noted that the interpenetration problem could be resolved with a suitable algorithm if it is assumed that each voxel set includes only occupied voxels. In such a case, it is algorithmically possible to always determine which voxels in voxel set A are in front of voxel set B based on the geometry of the voxel sets. It is often the case, however, that each voxel set contains both occupied voxels and unoccupied voxels, as illustrated in the case of the surface-based voxel model of an airplane object in FIG. 1. In a typical surface-based application, a voxel set may be up to about 90% empty, with only about 10% of voxels actually being occupied. If some voxels are empty, while other voxels within the same voxel set are occupied, then those empty voxels do not obstruct any view even if they are geometrically closer to the viewport, and therefore there is no need to consider empty voxels at all in rendering an image.
Accordingly, a need exists for a method and system that are capable of differentiating between occupied and empty voxels within each voxel set and dealing only with occupied voxels so as to address the interpenetration problem.